package _2_Linkedlist;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;

public class A24_reverseList {
    /*
    * 反转链表的方法有很多，这里写下要写什么方法
    * 1.递归
    * 2.双指针
    * */
    //双指针
    public ListNode reverseList(ListNode head) {
        ListNode cur = head, pre = null;
        while(cur != null) {
            ListNode tmp = cur.next; // 暂存后继节点 cur.next
            cur.next = pre;          // 修改 next 引用指向
            pre = cur;               // pre 暂存 cur
            cur = tmp;               // cur 访问下一节点
        }
        return pre;
    }
    //递归
    public ListNode reverseList2(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }

    public static void main(String[] args) {
        ListNode listNode = new ListNode(10);
        ListNode listNode2 = new ListNode(20);
        ListNode listNode3 = new ListNode(30);
        ListNode listNode4 = new ListNode(40);
        listNode.next = listNode2;
        listNode2.next = listNode3;
        listNode3.next = listNode4;
        A24_reverseList a24_reverseList = new A24_reverseList();
        a24_reverseList.reverseList(listNode);

    }
}
